
// 链队列（用链表存储的队列）

template<typename DataType>
struct Node
{
    DataType data;
    Node* next;
};

template <typename DataType>
class LinkQueue
{
public:
    LinkQueue();            // 初始化空的链队列
    LinkQueue(/* args */);  // 初始化非空链队列
    ~LinkQueue();           // 释放链队列的存储空间
    void EnQueue(DataType x);   // 入队操作，将元素x入队
    DataType DeQueue();         // 出队操作，将队头元素出队
    DataType GetHead();     // 获取队头元素
    int Empty();            // 判空
private:
    Node<DataType> *front, *rear;
};

template <typename DataType>
LinkQueue<DataType>::LinkQueue()
{
    Node<DataType> * s = nullptr;
    front = rear = s;       // 将队头指针和队尾指针都指向x
}

template <typename DataType>
LinkQueue<DataType>::~LinkQueue()
{
    // 就是单链表的析构，将每个节点循环遍历delete
}

template <typename DataType>
void LinkQueue<DataType>::EnQueue(DataType x)
{
    Node<DataType> * s =  nullptr;
    s = new Node<DataType>;         // 申请节点存储空间
    s->data = x;    s->next = nullptr;  // 填充节点内容
    rear->next = s;   rear = s;     // 队尾指针指向新节点
}

template <typename DataType>
DataType LinkQueue<DataType>::DeQueue()
{
    DataType x;
    Node<DataType> * p = nullptr;
    if (rear == front)
        throw "下溢";
    p = front->next; X = p->data;   // 暂存队头元素
    front->next = p->next;          // 将队头元素所在节点摘链
    if(p->next == nullptr)
        rear = front;        // 若出队前队列长度为1，则队列长度归零（首尾相同）
    delete p;
    return x;
}

